package com.lw.leetcode.sort.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * sort
 * 2003. 每棵子树内缺失的最小基因值
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/6 16:18
 */
public class SmallestMissingValueSubtree {

    public static void main(String[] args) {
        SmallestMissingValueSubtree test = new SmallestMissingValueSubtree();

        // {5,1,1,1}
//        int[] parents = {-1, 0, 0, 2};
//        int[] nums = {1, 2, 3, 4};

        // {7,1,1,4,2,1}
//        int[] parents = {-1, 0, 1, 0, 3, 3};
//        int[] nums = {5, 4, 6, 2, 1, 3};

        // {1,1,1,1,1,1,1}
//        int[] parents = {-1, 2, 3, 0, 2, 4, 1};
//        int[] nums = {2, 3, 4, 5, 6, 7, 8};

        // [6, 1, 1, 2, 2]
//        int[] parents = {-1, 4, 4, 4, 0};
//        int[] nums = {2, 4, 5, 1, 3};

        // [11,1,1,3,1,1,1,1,1,1]
//        int[] parents = {-1, 7, 7, 0, 6, 4, 0, 0, 1, 3};
//        int[] nums = {8, 9, 6, 1, 7, 3, 10, 4, 5, 2};

        // []
        //[]
        int[] parents = {-1, 59, 0, 30, 29, 79, 95, 4, 74, 85, 0, 7, 72, 9, 39, 50, 89, 49, 56, 9, 90, 89, 28, 27, 36, 29, 24, 60, 92, 95, 90, 37, 4, 72, 61, 23, 0, 4, 14, 73, 0, 11, 36, 81, 18, 29, 88, 35, 79, 74, 29, 10, 74, 22, 19, 92, 60, 73, 90, 0, 95, 17, 14, 0, 16, 42, 20, 60, 10, 30, 10, 14, 92, 36, 2, 85, 4, 92, 92, 42, 51, 90, 39, 4, 89, 95, 29, 28, 85, 2, 60, 40, 2, 10, 29, 0, 23, 30, 87, 52};
        int[] nums = {50, 29, 48, 83, 68, 99, 88, 75, 46, 47, 13, 78, 71, 80, 66, 5, 9, 25, 34, 96, 91, 20, 74, 93, 51, 2, 14, 15, 18, 62, 49, 1, 76, 44, 98, 63, 17, 90, 58, 94, 72, 85, 26, 87, 100, 59, 45, 55, 54, 81, 7, 43, 21, 97, 27, 69, 31, 84, 32, 53, 41, 28, 38, 24, 36, 82, 67, 61, 23, 79, 86, 3, 30, 12, 4, 33, 42, 56, 6, 95, 11, 92, 64, 70, 65, 35, 52, 39, 89, 60, 16, 57, 37, 73, 77, 40, 22, 8, 10, 19};

        int[] ints = test.smallestMissingValueSubtree(parents, nums);
        System.out.println(Arrays.toString(ints));
    }

    private Map<Integer, List<Integer>> map;
    private int[] arr;
    private int[] nums;
    private int[] keys;
    private int[] values;

    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        int length = parents.length;
        this.map = new HashMap<>();
        this.arr = new int[length];
        this.keys = new int[length];
        this.values = new int[length];
        this.nums = nums;
        for (int i = 0; i < length; i++) {
            map.computeIfAbsent(parents[i], v -> new ArrayList<>()).add(i);
        }
        find(0);
        return arr;
    }

    private TreeMap<Integer, Integer> find(int v) {
        int n = nums[v];
        List<Integer> list = map.get(v);
        if (list == null) {
            TreeMap<Integer, Integer> m = new TreeMap<>();
            m.put(n, n);
            arr[v] = n == 1 ? 2 : 1;
            return m;
        }
        int size = list.size();
        TreeMap<Integer, Integer> m = find(list.get(0));
        Map.Entry<Integer, Integer> floorEntry = m.floorEntry(n);
        Map.Entry<Integer, Integer> ceilingEntry = m.ceilingEntry(n);
        if (floorEntry != null && floorEntry.getValue() + 1 == n) {
            if (ceilingEntry != null && ceilingEntry.getKey() - 1 == n) {
                m.put(floorEntry.getKey(), ceilingEntry.getValue());
                m.remove(ceilingEntry.getKey());
            } else {
                m.put(floorEntry.getKey(), n);
            }
        } else {
            if (ceilingEntry != null && ceilingEntry.getKey() - 1 == n) {
                m.put(n, ceilingEntry.getValue());
                m.remove(ceilingEntry.getKey());
            } else {
                m.put(n, n);
            }
        }
        for (int i = 1; i < size; i++) {
            TreeMap<Integer, Integer> m2 = find(list.get(i));
            merge(m, m2);
        }
        Map.Entry<Integer, Integer> en = m.ceilingEntry(1);
        arr[v] = en.getKey() > 1 ? 1 : en.getValue() + 1;
        return m;
    }

    private void merge(TreeMap<Integer, Integer> m1, TreeMap<Integer, Integer> m2) {
        int size = m1.size();
        int i = 1;
        keys[0] = -2;
        values[0] = -2;
        for (Map.Entry<Integer, Integer> entry : m1.entrySet()) {
            keys[i] = entry.getKey();
            values[i] = entry.getValue();
            i++;
        }
        i = 1;
        while (i <= size) {
            int key = keys[i];
            int value = values[i];
            int lastValue = values[i - 1];
            Map.Entry<Integer, Integer> floorEntry = m2.floorEntry(key);
            if (floorEntry == null) {
                i++;
                continue;
            }
            if (floorEntry.getValue() + 1 == key) {
                if (floorEntry.getKey() - 1 == lastValue) {
                    m1.put(keys[i - 1], value);
                    m1.remove(key);
                    keys[i] = keys[i - 1];
                } else {
                    m1.put(floorEntry.getKey(), value);
                    m1.remove(key);
                    keys[i] = floorEntry.getKey();
                }
            } else {
                if (floorEntry.getKey() - 1 == lastValue) {
                    m1.put(keys[i - 1], floorEntry.getValue());
                    values[i - 1] = floorEntry.getValue();
                } else {
                    m1.put(floorEntry.getKey(), floorEntry.getValue());
                }
            }
            m2.remove(floorEntry.getKey());
        }

        int key = keys[size];
        int value = values[size];
        Map.Entry<Integer, Integer> ceilingEntry = m2.ceilingEntry(key);

        while (ceilingEntry != null) {
            if (ceilingEntry.getKey() - 1 == value) {
                m1.put(key, ceilingEntry.getValue());
                value = ceilingEntry.getValue();
                m2.remove(ceilingEntry.getKey());
            } else {
                m1.put(ceilingEntry.getKey(), ceilingEntry.getValue());
                key = ceilingEntry.getKey();
                value = ceilingEntry.getValue();
            }
            m2.remove(ceilingEntry.getKey());
            ceilingEntry = m2.ceilingEntry(key);
        }
    }

}
